﻿// 0817train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

/*
 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。
 请你从 nums 中找出并返回总和为 target 的元素组合的个数。

示例 1：
输入：nums = [1,2,3], target = 4
输出：7
 */

class Solution01
{
public:
    int track_sum = 0;
    int track_target;
    int result = 0;
    int combinationSum4(vector<int>& nums, int target) {
        track_target = target;
        backTrack(nums);
        return result;
    }
    void backTrack(vector<int>& nums)
    {
        if (track_sum== track_target)
        {
            result += 1;
        }
        if (track_sum > track_target)
        {
            return;
        }

        for (int i=0; i<nums.size();i++)
        {
            track_sum += nums[i];
            backTrack(nums);
            track_sum -= nums[i];
        }
	    
    }
};

/*
 题目描述
找到它是个小游戏，你需要在一个矩阵中找到给定的单词
假设给定单词HELLOWORLD，在矩阵中只要能找HELLOWORLD就算通过
注意区分英文字母大小写，并且你只能上下左右行走，不能走回头路

输入描述
输入第一行包含两个整数N M,N行M列的矩阵 (0 < N, M < 21)
分别表示N行M列的矩阵
第二行是长度不超过100的单词W
在整个矩阵中给定单词W只会出现一次
从第3行到第N+2是只包含大小写英文字母的长度为M的字符串矩阵

输出描述
如果能在矩阵中连成给定的单词，则输出给定单词首字母在矩阵中的位置为第几行第几列
否则输出 NO

示例1
输入
5 5
HELLOWORLD
CPUCY
EKLQH
CHELL
LROWO
DGRBC

输出
3 2
 */

class Solution02
{
public:
    vector<vector<int>>DirectionGrid = { {-1,0},{1,0},{0,-1},{0,1} };
    
    int row_size, col_size;
    int curr_index = 0; //此时要寻找的字符

    struct PathNode
    {
        int first, second, start_r, start_c;
        PathNode() = default;
        PathNode(int first, int second, int start_r, int start_c) :first(first), second(second), start_r(start_r), start_c(start_c) {}
    };
    queue<PathNode>bfs_queue;
    int curr_start_r, curr_start_c;
    void solve02(vector<vector<char>>&grid,string&target_str)
    {
        //1bfs_queue checked_grid(for循环中) DirectionGrid
        //条件判断，找到首字母塞进queue
        //for循环DirectionGrid，不越界，未访问，找到第二个字母
        row_size = grid.size();
        col_size = grid[0].size();

        vector<bool>checked_status(col_size, false);
        vector<vector<bool>>checked_grid(row_size, checked_status);

        for (int r=0; r<row_size; r++)
        {
            for (int c=0; c<col_size; c++)
            {
                char curr_char = grid[r][c];
                char target_char = target_str[curr_index];
                if (curr_char==target_char)
                {
                    PathNode path_node(r, c, r, c);
                    bfs_queue.push(path_node);
                    checked_grid[r][c] = true;
                }
            }
        }
        //更新目标char
        curr_index+=1;

        if (bfs_queue.empty())
        {
            cout << "NO";
            return;
        }

        while (!bfs_queue.empty())
        {
            if (curr_index==target_str.size())
            {
                //已经找到目标
                PathNode top_node = bfs_queue.front();
                bfs_queue.pop();
                curr_start_r = top_node.start_r;
                curr_start_c = top_node.start_c;
                break;
            }

            int q_size = bfs_queue.size();

            for (int i=0;i<q_size;i++)
            {
                PathNode top_node = bfs_queue.front();
                bfs_queue.pop();
                

                for (auto& dir_vec : DirectionGrid)
                {
                    int curr_r = top_node.first + dir_vec[0];
                    int curr_c = top_node.second + dir_vec[1];

                    //不越界 未访问 等于下一个目标char
                    bool is_curr_r = curr_r >= 0 && curr_r < row_size;
                    bool is_curr_c = curr_c >= 0 && curr_c < col_size;

                    if (is_curr_r && is_curr_c)
                    {
                        bool is_visited = checked_grid[curr_r][curr_c];
                        char curr_char = grid[curr_r][curr_c];
                        bool is_available = curr_char == target_str[curr_index];
                        if (!is_visited && is_available)
                        {
                            //加入bfs，标记已访问
                            PathNode path_node(curr_r, curr_c, top_node.start_r, top_node.start_c);
                            bfs_queue.push(path_node);
                            checked_grid[curr_r][curr_c] = true;
                        }
                    }

                }

                //q_size------
            }
            if (!bfs_queue.empty())
            {
                curr_index++;
            }
            //while (!bfs_queue.empty())
        }

        if (curr_index==target_str.size())
        {
            cout << curr_start_r+1 << ' ' << curr_start_c+1;
            return;
        }
        cout << "NO";
        //solve02
    }

};

class Solution21
{
public:
    int row_size, col_size;
    vector<vector<int>>DirectionGrid = { {-1,0},{1,0},{0,-1},{0,1} };
    string track_target;
    bool is_find = false;
    int track_index = 0;
    void backTrack(vector<vector<char>>& grid, vector<vector<bool>>&checked, 
        int prev_r, int prev_c
    )
    {
        if (track_index==track_target.size())
        {
            //注意，找到的时候，一定要加一个标志位判断，
            //回溯会层层退出，最终走出回溯，回到主函数时，track_index会重新回到1
            is_find = true;
            //说明已经找到了
            return;
        }

        for (auto&dir_vec:DirectionGrid)
        {
            int curr_r = prev_r + dir_vec[0];
            int curr_c = prev_c + dir_vec[1];

            //未越界，未访问，==tarck_target[track_index]
            bool is_curr_r = curr_r >= 0 && curr_r < row_size;
            bool is_curr_c = curr_c >= 0 && curr_c < col_size;

            if (is_curr_r&&is_curr_c)
            {
                bool is_visited = checked[curr_r][curr_c];
                char curr_char = grid[curr_r][curr_c];
                bool is_available = curr_char == track_target[track_index];
                if (!is_visited && is_available)
                {
                    checked[curr_r][curr_c] = true;
                    track_index++;
                    backTrack(grid, checked, curr_r, curr_c);
                    checked[curr_r][curr_c] = false;
                    track_index--;
                    
                }

            }

        }

    }

    void solve21(vector<vector<char>>&grid, string target_str)
    {
        row_size = grid.size();
        col_size = grid[0].size();
        track_target = target_str;

        for (int r=0; r<row_size; r++)
        {
            for (int c=0; c<col_size; c++)
            {
                vector<bool>checked_status(col_size, false);
                vector<vector<bool>>checked(row_size, checked_status);

                
                if (grid[r][c]== target_str[0])
                {
                    track_index = 1;
                    checked[r][c] = true;
                    backTrack(grid, checked, r, c);
                    checked[r][c] = false;

                }


                //if (track_index == track_target.size())
                if (is_find)
                {
                    cout << r + 1 << ' ' << c + 1;
                    return;
                }
                

            }

        }
        cout << "NO";
        //solve21
    }

};

int main()
{
    /*
5 5
HELLOWORLD
CPUCY
EKLQH
CHELL
LROWO
DGRBC
     */
    {
        //两个整数N M, N行M列的矩阵
        string target_str = "HELLOWORLD";
        vector<string>origin_vec = {"CPUCY","EKLQH","CHELL","LROWO","DGRBC"};
        //int row_size, col_size;
        //cin >> row_size >> col_size;

        //string target_str;
        //cin >> target_str;

        //vector<string>origin_vec(row_size);
        //for (int i=0;i<row_size; i++)
        //{
        //    cin >> origin_vec[i];
        //}

        vector<vector<char>>grid;

        for (auto&oh_str:origin_vec)
        {
            vector<char>mini_char_vec;
            for (auto&oh_char:oh_str)
            {
                mini_char_vec.push_back(oh_char);
            }
            grid.push_back(mini_char_vec);
        }

        Solution21 solu;
        solu.solve21(grid, target_str);

        return 0;
    }
    //nums = [1,2,3], target = 4
    vector<int>nums = { 1,2,3 };
    int target = 4;
    Solution01 solu;
    cout << solu.combinationSum4(nums, target);
    
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
